#include <stdio.h>
#define ERROR -1

#define MAXTABLESIZE 100000  /* 允许开辟的最大散列表长度 */
typedef int ElementType;     /* 关键词类型用整型 */
typedef int Index;           /* 散列地址类型 */
typedef Index Position;      /* 数据所在位置与散列地址是同一类型 */
/* 散列单元状态类型，分别对应：有合法元素、空单元、有已删除元素 */
typedef enum { Legitimate, Empty, Deleted } EntryType;

typedef struct HashEntry Cell; /* 散列表单元类型 */
struct HashEntry{
    ElementType Data; /* 存放元素 */
    EntryType Info;   /* 单元状态 */
};

typedef struct TblNode *HashTable; /* 散列表类型 */
struct TblNode {   /* 散列表结点定义 */
    int TableSize; /* 表的最大长度 */
    Cell *Cells;   /* 存放散列单元数据的数组 */
};

HashTable BuildTable();//创建哈希表
Position Find( HashTable H, ElementType Key );//线性检测查找

Position Hash( ElementType Key, int TableSize )//找到对应存储位置
{
    if(Key==-1)//如果是-1代表为空从头开始遍历
        return 0;
    return (Key % TableSize);
}

int main()
{
    HashTable H;
    ElementType Key;
    Position P;
    H = BuildTable();//构建哈希表
    scanf("%d", &Key);//输入要查找的值
    P = Find(H, Key);//通过查找函数返回对应信息
    if (P==ERROR)//如果返回值为ERROR
        printf("ERROR: %d is not found and the table is full.\n", Key);
    else if (H->Cells[P].Info == Legitimate)//如果找到
        printf("%d is at position %d.\n", Key, P);
    else//如果没找到，哈希表没有存满，返回第一个空单元的位置下标
        printf("%d is not found.  Position %d is returned.\n", Key, P);

    return 0;
}
HashTable BuildTable() {//创建哈希表
    int TableSize, n;
    HashTable H;
    scanf("%d", &TableSize);  // 从标准输入中读取哈希表的大小
    /* 为哈希表分配内存 */
    H = (HashTable) malloc(sizeof(struct TblNode));
    H->TableSize = TableSize;
    H->Cells = (Cell *) malloc(sizeof(struct HashEntry) * H->TableSize);
    /* 初始化哈希表的单元状态为Empty */
    for (int i = 0; i < H->TableSize; i++) {
        H->Cells[i].Info = Empty;
    }
    for (int i = 0; i < TableSize; i++) {
        scanf("%d", &n);
        int a = Hash(n, TableSize);
        while (H->Cells[a].Data == -1 || H->Cells[a].Info == Legitimate) //遇到数据是-1的结点跳过
        {
            a=(a+1)%TableSize;//用求余的形式预防超过Size的情况
        }
        H->Cells[a].Data = n;
        if (H->Cells[a].Data == -1)
            H->Cells[a].Info = Empty;//如果为-1将-1存入表但其状态显示为空
        else
            H->Cells[a].Info = Legitimate;

    }
        return H;  // 返回构建好的哈希表
    }
Position Find(HashTable H, ElementType Key) {//通过线性检测的查找函数
    int a = Key % H->TableSize;
    int t=0;
    int flag=0;//预防先碰见-1时，直接返回ERROR
    for(int i=0;i != H->TableSize;i++) {
        if (H->Cells[a].Data == Key)//找到key值返回位置
            return a;
        if(H->Cells[a].Info==Empty&&flag==0){//记录有空存储单元的位置
            t=a;
            flag=1;
        }
        a = (a + 1) % H->TableSize;//找到下一个取余没有数据的位置
    }
        if (flag==1)
            return t;
        else
            return ERROR;
}
